# -*- encoding:utf-8 -*-

from utilitybelt import secure_randint as randint

def egcd(a,b):
    if a == 0:
        return (b,0,1)
    else:
        g,y,x = egcd(b % a,a)
        return (g,x - (b // a) * y,y)

'''
    这是一个迭代的函数，扩展欧几里德算法，求得最大公约数
    // 是取整运算，
    % 是取模运算
'''

def mod_inverse(k,prime):
    k = k % prime
    if k < 0:
        r = egcd(prime,-k)[2]
    else:
        r = egcd(prime,k)[2]
    return (prime + r) % prime      # 结果恒大于 0

'''
    扩展欧几里德算法求模反元素

    a*x + b*y = 1 解方程得到 y 在 （mod a）时得到的逆元
'''

def random_ploynomial(degree,intercept,upper_bound):
    if degree < 0:
        raise ValueError('阶数不能为负数')
    coefficients = [intercept]
    for i in range(degree):
        random_coeff = randint(0,upper_bound-1)
        coefficients.append(random_coeff)
    return coefficients

'''
    生成随机多项式，传入参数为 阶数，常数（截距），上限

    返回系数
'''

def get_ploynomial_points(coefficient,num_points,prime):
    points = []
    for x in range(1,number):
        y = coefficients[0]
        for i in range(1,len(coefficients)):
            exponentiation = (x**i) % prime
            term = (coefficients[i] * exponentiation) % prime
            y = (y + term) % prime

        points.append((x,y))
    return points

'''
    计算多项式每一项的值
'''
def modular_lagrange_interpolation(x, points, prime):
    # 将得到tuple列表中的x和y取出来，是unzip的一个过程
    x_values, y_values = zip(*points)
    # x_values,y_values 均为列表
    # 初始化函数f(x),并计算: f(x) = SUM( y_i * l_i(x) )
    f_x = 0
    for i in range(len(points)):
        # 估算拉格朗日多项式插值基函数 l_i(x)
        numerator, denominator = 1, 1
        # 分子、分母初始化
        for j in range(len(points)):
            # 如果 i == j,则没有必要计算这个多项式（为什么？）
            if i == j:
                continue
            # 否则更新分子分母
            numerator = (numerator * (x - x_values[j])) % prime
            denominator = (denominator * (x_values[i] - x_values[j])) % prime

        # 拉格朗日多项式是 分子 + 分母 取 mod（大素数）的逆元（为什么？）
        lagrange_polynomial = numerator * mod_inverse(denominator, prime)
        # multiply the current y & the evaluated polynomial & add it to f(x)
        # 把当下的 y 的值和拉格朗日的这一项相乘 ，加到 f(x) 中
        f_x = (prime + f_x + (y_values[i] * lagrange_polynomial)) % prime
    return f_x

'''
拉格朗日插值函数
'''